/*
题目描述
有n个人围成一圈，顺序从1开始排号。
从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。
要求用循环链表实现。

输入
只有一个正整数n，保证n不超过1000。

输出
输出最后留下的人的原始编号。
请注意行尾输出换行。
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct people
{
    int id;
    struct people *next;
} People;

People *createNode(int id)
{
    People *newNode = (People *)malloc(sizeof(People));
    newNode->id = id;
    newNode->next = NULL;
    return newNode;
}

People *insertNode(People *List, int id)
{
    People *newNode = createNode(id);
    People *head = List;
    People *current = List;
    while (1)
    {
        // 新结点最小
        if (id < current->id)
        {
            newNode->next = current;
            current = current->next;
            while (current->next != head)
            {
                current = current->next;
            }
            current->next = newNode;
            return newNode;
        }
        // 新结点在范围内
        else
        {
            if (id < current->next->id)
            {
                newNode->next = current->next;
                current->next = newNode;
                return head;
            }
            else
            {
                current = current->next;
            }
            // 新结点最大
            if (current->next == head)
            {
                newNode->next = head;
                current->next = newNode;
                return head;
            }
        }
    }
}

People *deleteNode(People *List, int id)
{
    // 只有一个元素时不允许删除
    if (List->next == List)
    {
        return NULL;
    }
    People *head = List;
    People *current = List;
    while (1)
    {
        if (current->next->id == id)
        {
            People *t = current->next;
            current->next = current->next->next;
            free(t);
            // free(current);
            return head;
        }
        else
        {
            current = current->next;
        }
        if (current->next == head && current->next->id == id)
        {
            People *t = current->next;
            current->next = current->next->next;
            free(t);
            return current->next;
        }
    }
}

People *buildList()
{
    int n;
    scanf("%d", &n);
    People *head = createNode(1);
    head->next = head;
    for (int i = 1; i < n; i++)
    {
        head = insertNode(head, i + 1);
    }
    return head;
}

void printList(People *List)
{
    People *head = List;
    People *current = List;
    printf("%d\n", current->id);
    current = current->next;
    while (current != head)
    {
        printf("%d\n", current->id);
        current = current->next;
    }
}

int main()
{
    People *List = buildList();
    // printList(List);1
    int num = 1;
    People *current = List;
    while (List->next != List)
    {
        if (num % 3 == 0)
        {
            // 删除结点后current被释放，不能直接将current->id传入delete
            People *p = current;
            current = current->next;
            List = deleteNode(List, p->id);
        }
        else
        {
            current = current->next;
        }
        num++;
    }
    printf("%d\n", List->id);
}